package 链表;

/**
 * @Author Weton Li
 * @Date 2021/3/14 10:50
 */
public class 一_反转链表 {

    public static ListNode reverseListRecursion(ListNode head){

        if (head.next == null || head == null) {
            return head;
        }
        ListNode resHead = head.next;

        ListNode reverseRes = reverseListRecursion(resHead);

        resHead.next = head;

        head.next = null;

        return reverseRes;

    }
    public static ListNode reverseList(ListNode head) {

        ListNode prev = null; // 前指针

        ListNode tempNextNode = null; // 临时的下一个节点

        ListNode curNode = head; // 当前节点，即为头结点

        while (curNode != null) {
            tempNextNode = curNode.next;
            curNode.next = prev; // 当前节点的下一个节点指向 前一个节点指针（断链）
            prev = curNode; // 前一个节点指针向后移动，即移动到当前节点
            curNode = tempNextNode; // 当前的头结点即为下一个临时保存的节点
        }
        return prev;
    }

    public static void printListNode(ListNode head) {
        ListNode curr = head;

        while (curr != null) {
            System.out.print(curr.value + "->");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(5);
        ListNode listNode4 = new ListNode(7);
        listNode1.next = listNode2; // 使两节点相连接
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = null;

        printListNode(listNode1);

//        printListNode(reverseList(listNode1));

        printListNode(reverseListRecursion(listNode1));

    }
}
